#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Serialization;
using System.Security.Permissions;
using System.Xml.Serialization;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a node in a <see cref="BinaryTree&lt;T&gt;"/>.
    /// </summary>
    /// <typeparam name="T">The type of the data associated with the node.</typeparam>
    [Serializable]
    public class BinaryTreeNode<T> : AbstractNode<T>
    {
        /// <summary>
        /// Color of the node. This field is for <see cref="RedBlackTree&lt;T&gt;"/> only.
        /// The default color is Red.
        /// </summary>
        [CLSCompliant(false)]
        protected internal NodeColor _Color = NodeColor.Red;

        /// <summary>
        /// Left child of this instance.
        /// </summary>
        [CLSCompliant(false)]
        protected internal BinaryTreeNode<T> _Left;

        /// <summary>
        /// Level associated with this instance.
        /// </summary>
        [CLSCompliant(false)]
        protected internal int _Level;

        /// <summary>
        /// Right child of this instance.
        /// </summary>
        [CLSCompliant(false)]
        protected internal BinaryTreeNode<T> _Right;

        /// <summary>
        /// Initializes a new instance of the <see cref="BinaryTreeNode&lt;T&gt;"/> class.
        /// </summary>
        public BinaryTreeNode()
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BinaryTreeNode&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="data">The data associated with the node.</param>
        public BinaryTreeNode(T data)
            : base(data)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BinaryTreeNode&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="data">The data associated with the node.</param>
        /// <param name="left">The left child node.</param>
        /// <param name="right">The right child node.</param>
        public BinaryTreeNode(T data, BinaryTreeNode<T> left, BinaryTreeNode<T> right)
            : base(data)
        {
            Left = left;
            Right = right;
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BinaryTreeNode&lt;T&gt;"/> class.
        /// </summary>
        /// <param name = "info">The <see cref = "T:System.Runtime.Serialization.SerializationInfo" /> to populate with data.
        /// </param>
        /// <param name = "context">The destination (see <see cref = "T:System.Runtime.Serialization.StreamingContext" />) for this serialization.
        /// </param>
        protected BinaryTreeNode(SerializationInfo info, StreamingContext context)
            : base(info, context)
        {
            Value = info.GetValue("Value", typeof (T)) is T ? (T) info.GetValue("Value", typeof (T)) : default(T);
            Left = info.GetValue("Left", typeof (BinaryTreeNode<T>)) as BinaryTreeNode<T>;
            Right = info.GetValue("Right", typeof (BinaryTreeNode<T>)) as BinaryTreeNode<T>;
            Parent = info.GetValue("Parent", typeof (BinaryTreeNode<T>)) as BinaryTreeNode<T>;
            Balance = (int) info.GetValue("Balance", typeof (int));
            Depth = (int) info.GetValue("Depth", typeof (int));
            _Level = (int) info.GetValue("Level", typeof (int));
            _Color = (NodeColor) info.GetValue("Color", typeof (NodeColor));
        }

        /// <summary>
        /// Gets or sets the left child of the node.
        /// </summary>
        /// <value>The left child.</value>
        public BinaryTreeNode<T> Left
        {
            get { return _Left; }
            set
            {
                _Left = value;
                if (_Left != null)
                {
                    _Left.Depth = Depth + 1;
                    _Left.Parent = this;
                }
                if (Tree == null) return;
                Tree.OnNodeChange(this);
                if (_Left != null) Tree.OnNodeChange(_Left);
            }
        }

        /// <summary>
        /// Gets or sets the right child of the node.
        /// </summary>
        /// <value>The right child.</value>
        public BinaryTreeNode<T> Right
        {
            get { return _Right; }
            set
            {
                _Right = value;
                if (_Right != null)
                {
                    _Right.Depth = Depth + 1;
                    _Right.Parent = this;
                }
                if (Tree == null) return;
                Tree.OnNodeChange(this);
                if (_Right != null) Tree.OnNodeChange(_Right);
            }
        }

        /// <summary>
        /// Gets or sets the balance of this instance.
        /// </summary>
        /// <value>The balance associated with the node.</value>
        public int Balance { get; protected internal set; }

        /// <summary>
        /// Gets or sets the tree which contains this instance.
        /// </summary>
        /// <value>The host binary tree.</value>
        [XmlIgnore]
        public IBinaryTree<T> Tree { get; set; }

        /// <summary>
        /// Gets a value indicating whether this instance is a left child.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if this instance is a left child; otherwise, <c>false</c>.
        /// </value>
        public bool IsLeftChild
        {
            get { return !IsRoot() && ReferenceEquals(this, ((BinaryTreeNode<T>) Parent).Left); }
        }

        /// <summary>
        /// Gets a value indicating whether this instance is a right child.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if this instance is a right child; otherwise, <c>false</c>.
        /// </value>
        public bool IsRightChild
        {
            get { return !IsRoot() && ReferenceEquals(this, ((BinaryTreeNode<T>) Parent).Right); }
        }

        /// <summary>
        /// Gets a value indicating whether this instance has a left child.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if this instance has a left child; otherwise, <c>false</c>.
        /// </value>
        public bool HasLeftChild
        {
            get { return Left != null; }
        }

        /// <summary>
        /// Gets a value indicating whether this instance has a right child.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if this instance has a right child; otherwise, <c>false</c>.
        /// </value>
        public bool HasRightChild
        {
            get { return Right != null; }
        }

        /// <summary>
        /// Gets all the descendant nodes in a order specified by <see cref="BinaryTreeTraversalOrder"/>.
        /// </summary>
        /// <param name="traversalOrder">Order of the tree traversal.</param>
        /// <returns>All descendant nodes of this instance.</returns>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="traversalOrder"/> is null.</exception>
        public IEnumerable<BinaryTreeNode<T>> ToEnumerable(BinaryTreeTraversalOrder traversalOrder)
        {
            switch (traversalOrder)
            {
                case BinaryTreeTraversalOrder.PreOrder:
                    return ToPreOrderEnumerable();
                case BinaryTreeTraversalOrder.PostOrder:
                    return ToPostOrderEnumerable();
                case BinaryTreeTraversalOrder.InOrder:
                    return ToInOrderEnumerable();
                case BinaryTreeTraversalOrder.DepthFirst:
                    return ToDepthFirstEnumerable();
                case BinaryTreeTraversalOrder.BreadthFirst:
                    return ToBreadthFirstEnumerable();
                default:
                    throw new ArgumentOutOfRangeException("traversalOrder");
            }
        }

        /// <summary>
        /// Fetches all the descendant nodes in Depth-First fashion.
        /// </summary>
        /// <returns>
        /// A collection of nodes ordered in depth-first fashion.
        /// </returns>
        protected IEnumerable<BinaryTreeNode<T>> ToDepthFirstEnumerable()
        {
            return ToPreOrderEnumerable();
        }

        /// <summary>
        /// Fetches all the descendant nodes in Breadth-First fashion.
        /// </summary>
        /// <returns>
        /// A collection of nodes ordered in breadth-first fashion.
        /// </returns>
        protected IEnumerable<BinaryTreeNode<T>> ToBreadthFirstEnumerable()
        {
            var queue = new Queue<BinaryTreeNode<T>>();
            queue.Enqueue(this);

            while (0 < queue.Count)
            {
                BinaryTreeNode<T> node = queue.Dequeue();
                if (node != null)
                {
                    if (node.Left != null) queue.Enqueue(node.Left);
                    if (node.Right != null) queue.Enqueue(node.Right);
                }
                yield return node;
            }
        }

        /// <summary>
        /// Fetches all the descendant nodes in Pre-Order fashion.
        /// </summary>
        /// <returns>
        /// A collection of nodes ordered in pre-order fashion.
        /// </returns>
        protected IEnumerable<BinaryTreeNode<T>> ToPreOrderEnumerable()
        {
            yield return this;

            if (Left != null)
                foreach (var binaryTreeNode in Left.ToPreOrderEnumerable())
                {
                    yield return binaryTreeNode;
                }

            if (Right != null)
                foreach (var binaryTreeNode in Right.ToPreOrderEnumerable())
                {
                    yield return binaryTreeNode;
                }
        }

        /// <summary>
        /// Fetches all the descendant nodes in In-Order fashion.
        /// </summary>
        /// <returns>
        /// A collection of nodes ordered in in-order fashion.
        /// </returns>
        protected IEnumerable<BinaryTreeNode<T>> ToInOrderEnumerable()
        {
            if (Left != null)
                foreach (var binaryTreeNode in Left.ToInOrderEnumerable())
                {
                    yield return binaryTreeNode;
                }

            yield return this;

            if (Right != null)
                foreach (var binaryTreeNode in Right.ToInOrderEnumerable())
                {
                    yield return binaryTreeNode;
                }
        }

        /// <summary>
        /// Fetches all the descendant nodes in Post-Order fashion.
        /// </summary>
        /// <returns>
        /// A collection of nodes ordered in post-order fashion.
        /// </returns>
        protected IEnumerable<BinaryTreeNode<T>> ToPostOrderEnumerable()
        {
            if (Left != null)
                foreach (var binaryTreeNode in Left.ToPostOrderEnumerable())
                {
                    yield return binaryTreeNode;
                }

            if (Right != null)
                foreach (var binaryTreeNode in Right.ToPostOrderEnumerable())
                {
                    yield return binaryTreeNode;
                }

            yield return this;
        }

        /// <summary>
        /// Deletes this instance and its descendants.
        /// </summary>
        public void Delete()
        {
            if (Left != null) Left.Delete();
            if (Right != null) Right.Delete();
            Left = null;
            Right = null;
            Value = default(T);
        }

        /// <summary>
        ///   Determines whether the specified node is a sibling of this instance.
        /// </summary>
        /// <param name = "node">The sibling node.</param>
        /// <returns>
        ///   <c>true</c> if the specified node is sibling; otherwise, <c>false</c>.
        /// </returns>
        public bool IsSibling(BinaryTreeNode<T> node)
        {
            if (Parent != null)
            {
                var binaryParent = (BinaryTreeNode<T>) Parent;
                return IsLeftChild ? binaryParent.Right.Equals(node) : binaryParent.Left.Equals(node);
            }
            return false;
        }

        /// <summary>
        /// Determines whether any descendant nodes of this instance contain the <paramref name="data"/>.
        /// </summary>
        /// <param name="data">The data to search in the descendant nodes.</param>
        /// <returns><see cref="BinaryTreeNode&lt;T&gt;"/> if the specified value is found; otherwise, <c>null</c>.
        /// </returns>
        public virtual BinaryTreeNode<T> HasDescendant(T data)
        {
            return ToDepthFirstEnumerable().FirstOrDefault(node => node.Value.Equals(data));
        }

        /// <summary>
        /// Determines whether the specified node is a descendant of this instance.
        /// </summary>
        /// <param name="node">The node to search in the descendant nodes.</param>
        /// <returns>
        /// 	<c>true</c> if the specified node has child; otherwise, <c>false</c>.
        /// </returns>
        public virtual bool HasDescendant(BinaryTreeNode<T> node)
        {
            return ToDepthFirstEnumerable().Contains(node);
        }

        /// <summary>
        /// Adds the <paramref name="node"/> as a child of this instance.
        /// </summary>
        /// <param name="node">The child node.</param>
        /// <remarks>It tries to insert the node as left-child first, but if the place 
        /// is already occupied it tries to insert the node at the right. If the right
        /// is also occupied then it will throw <see cref="InvalidOperationException"/></remarks>
        /// <exception cref="InvalidOperationException">Both left and right positions are occupied.</exception>
        public void AddChild(BinaryTreeNode<T> node)
        {
            if (Left == null)
                Left = node;
            else if (Right == null)
                Right = node;
            else
                throw new InvalidOperationException(string.Format(LanguageResource.NoEmptyPlaceToAdd, node));
        }

        #region Overrides of AbstractNode<T>

        /// <summary>
        /// Gets a value indicating whether this instance is a leaf node.
        /// </summary>
        /// <value><c>true</c> if this instance is leaf node; otherwise, <c>false</c>.</value>
        public override bool IsLeaf
        {
            get { return (Left == null && Right == null); }
        }

        /// <summary>
        /// Gets the child node count of the node.
        /// </summary>
        /// <value>The child node count.</value>
        public override int ChildCount
        {
            get
            {
                if (Left != null && Right != null)
                    return 2;
                if (Left == null && Right == null)
                    return 0;
                return 1;
            }
        }

        /// <summary>
        /// Determines whether the current instance is equal to <paramref name="other"/> or not.
        /// </summary>
        /// <param name="other">The other node.</param>
        /// <returns>
        /// <c>true</c> if this instance is equal to <paramref name="other" />; otherwise, <c>false</c>.
        /// </returns>
        public override bool Equals(AbstractNode<T> other)
        {
            if (other == null) return false;
            if (!(other is BinaryTreeNode<T>)) return false;
            if (ReferenceEquals(this, other)) return true;
            if (Value.Equals(other.Value))
            {
                // check if right child is not null then if it is equals to the other's right child or not. If right child is null
                // then check if other's right child is also null or not and same goes for the left child also.
                bool isRightEqual = (Right != null)
                                        ? Right.Equals(((BinaryTreeNode<T>) other).Right)
                                        : (((BinaryTreeNode<T>) other).Right == null);
                bool isLeftEqual = (Left != null)
                                       ? Left.Equals(((BinaryTreeNode<T>) other).Left)
                                       : (((BinaryTreeNode<T>) other).Left == null);
                return isLeftEqual && isRightEqual;
            }
            return false;
        }

        /// <summary>
        ///   Populates a <see cref = "T:System.Runtime.Serialization.SerializationInfo" /> with the data needed to serialize the target object.
        /// </summary>
        /// <param name = "info">The <see cref = "T:System.Runtime.Serialization.SerializationInfo" /> to populate with data.
        /// </param>
        /// <param name = "context">The destination (see <see cref = "T:System.Runtime.Serialization.StreamingContext" />) for this serialization.
        /// </param>
        /// <exception cref = "T:System.Security.SecurityException">The caller does not have the required permission.
        /// </exception>
        [SecurityPermission(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
        public override void GetObjectData(SerializationInfo info, StreamingContext context)
        {
            info.SetType(typeof (BinaryTreeNode<T>));
            info.AddValue("Value", Value);
            info.AddValue("Left", Left);
            info.AddValue("Right", Right);
            info.AddValue("Parent", Parent);
            info.AddValue("Balance", Balance);
            info.AddValue("Depth", Depth);
            info.AddValue("Level", _Level);
            info.AddValue("Color", _Color);
        }

        #endregion
    }
}